perm filename OCCULT[00,BGB] blob
sn#115054 filedate 1974-08-20 generic text, type C, neo UTF8
COMMENT ⊗ VALID 00010 PAGES
C REC PAGE DESCRIPTION
C00001 00001
C00003 00002 {⊂C<N αOCCULT λ30 P47 I425,0 JC FA} SECTION 4.
C00009 00003
C00011 00004 ⊂4.1 Initialization for Hidden Line Elimination.⊃
C00017 00005 ⊂4.2 Hide Marking a Coherent Object.⊃
C00022 00006 ⊂4.3 Edge-Edge and Face-Vertex Comparing.⊃
C00025 00007 An alternate edge-edge compare method would be to solve the
C00028 00008 ⊂4.4 Recursive Windowing.⊃
C00032 00009 ⊂4.5 Photometric Modeling and Video Generation.⊃
C00035 00010 ⊂4.6 Performance of OCCULT and Related Work.⊃
C00037 ENDMK
C⊗;
{⊂C;<N; αOCCULT; λ30; P47; I425,0; JC; FA} SECTION 4.
{JC; FD} HIDDEN LINE ELIMINATION FOR COMPUTER VISION.
{λ7; W250; JA; FA}
4.0 Introduction to Hidden Line Elimination.
4.1 Initialization for Hidden Line Elimination.
4.2 Hide Marking a Coherent Object.
4.3 Edge-Edge and Face-Vertex Comparing.
4.4 Recursive Windowing.
4.5 Photometric Modeling and Video Generation.
4.6 Performance of OCCULT and Related Work.
{λ30;W0;I950,0;JUFA}
⊂4.0 Introduction to Hidden Line Elimination.⊃
Hidden line elimination refers to the process of simulating
the appearance of opaque three dimensional objects. The phrase
<hidden line elimination> dates from when the problem only involved
deleting the undesired, that is the <hidden> lines, from a line
drawing; today the phrase persists but connotes the wider problem of
synthesizing realistic images using a computer. The present
discussion is about techniques which have been implemented in a
particular hidden line eliminator named OCCULT, since the word
<OCCULT> means <to hide>. Employing the GEOMED routines and the
winged edged polyhedron representation, OCCULT illustrates novel
solutions to the graphics problems of exploiting object coherence and
image coherence, of combining image space and model space
techniques, and of spatial sorting of faces, edges and vertices in
two dimensions.
OCCULT is further characterized by its intended application
to computer vision and robotics. The distinguishing design
requirement of a hidden line eliminator intended for verification
vision is that it must maintain back pointers from the final 2-D
images to the initial 3-D models so that the identity of image
features can be recovered. In computer graphics, the results of
hidden line elimination are intended for human viewing so the
correspondence between the image and the model is not retained.
Another design goal for OCCULT was to output a coherent graph of
regions, edges and vertices that covered the image with no holes
missing, no regions overlapping and no dangling edges. It was
naively assumed that such a highly structured image representation,
called a <mosaic image>, would provide a suitable basis for deriving
data such as the location and orientation of high contrast edges
without having to generate video images.
The idea of using a hidden line eliminator in a vision system
is not new and has appeared in two other vision systems, one by
[Roberts] and one by [Falk]; the present system is a direct heir of
the work of both Roberts and Falk in that the last version of the
Falk system contained one of the early versions of OCCULT (as
installed by Richard Orban). I reject the view that the hidden line
elimination problem has been adequately solved; as with image
anaylsis, image synthesis (i.e. hidden line elimination), is going to
continue to be a perenial research problem because it can not be
fully isolated from physical modeling. Metaphorically, hidden line
elimination is the visible tip of the iceberg of physical simulation.
The weaknesses of the underlying model literally show up in passing
through the process of image synthesis. The present day collection
of techniques are still quite lacking in realism, economy,
flexibility and even reliability.
OCCULT is not a simple hidden line eliminator. In overall
strucuture OCCULT is a three level hierarcy of methods. At the outer
level there is a [Warnock] like recursive window method, which calls
an Edge-Edge compare method on small enough windows which in turn
calls a Coherent Object method to trace and mark the portions of an
object that are hidden. Appended to the trilevel hierarcy are four
auxillary techniques: initial elimination by clipping planes, initial
elimination by face vectors, initial elimination by inspection of
concave corners, and a final elimination of potential special cases
(missed by edge-edge methods) using a pseudo face-vertex method. The
challenging part in building an OCCULT like hidden line eliminator is
getting all the unruly beasts in harness together; the intriguing
mystery is that no one beast is sufficiently stronger than all the
rest to carry the whole burden expeditiously.{Q}
⊂4.1 Initialization for Hidden Line Elimination.⊃
A substantial part of sophisticated hidden line elimination
lies in careful attention to initial preparations. As it has now
stood for the past two years, OCCULT has two input restrictions
imposed for the sake of execution speed: no conflicting bodies are
allowed and no concave faces are allowed. Conflicting bodies are
those that occupy the same space at the same time; concave faces are
faces with interiors containing a pair of points such that the line
segment between the points is not contained in the face. The
rational for both these restrictions is based on the optimization
technique of getting computations out of inner loops - conflicting
bodies and concave faces can be eliminated by employing certain
polyhedral construction primitives prior to hidden line elimination.
The restrictions are not inherent limitations of any of the
techniques in OCCULT, so that a more unrestricted but slower
implementation is feasible.
OCCULT is essentially a marking algorithm, two of the marking
bits carried in the status word of every face, edge and vertex are
the POTENT bit indicating that an entity is potentially visible and
the VISIBLE bit indicating that an entity is actually visible. The
combination (¬POTENT and ¬VISIBLE) means that the entity has been
found to be hidden, the combination (POTENT and VISIBLE) is an
unused state that happens to be interpreted as VISIBLE. The
initialization can be regarded as three marking steps: (1). vertex
marking and vertex perspective projection; (2). face marking, face
Z-clipping, and computation of face coefficients; and (3). edge
marking and computation of edge coefficients.
Vertex initialization includes the prespective projection of
every vertex in the model and the marking of every vertex that is in
front of the camera as POTENT (potentially visible) with ZPP(V)
greater than FOCAL. Two further status bits, named PZZ and NZZ,
indicating positive Zpp or negative Zpp are IOR'ed into all the faces
and edges of the vertex for the sake of the Z-clipper.
Face initialization consists of Z-clipping: if the face has
only its NZZ bit is on then it is completely behind the camera and is
immediate dropped from all futher condsideration; if the face has
both its PZZ and its NZZ turn on then it is Z-clipped by using the
camera's image plane as a cutting plane. Next for faces in view of
the camera, the 3-D perspective projected face coefficients are
computed and faces with their backsides towards the camera are
dropped, and faces surviving to this point are marked as POTENT and
are placed into a list of faces of the first window of the recursive
window sort.
Edge initialization consists of computing the normalized 2-D
edge coefficients (for the sake of rapid edge-edge compares) and
marking the edge as FOLDED or ¬FOLDED depending on whether it has one
face POTENT or two faces POTENT. FOLDED edges are then inverted if
necessary so that the POTENT face is the PFACE. Inspite of the
complexity explained so far, still further measures could be taken to
make the hidden line elimintator even faster, For example more 3-D
clipping or spatial recusive cell sorting would allow the early
elimination of objects that fall outside of purview.
{JC} Normalized 2-D Edge Coefficients:{λ10;JAF3}
AA(E) ← YPP(PVT(E)) - YPP(NVT(E));
BB(E) ← XPP(NVT(E)) - XPP(PVT(E));
CC(E) ← XPP(PVT(E))*YPP(NVT(E)) - XPP(NVT(E))*YPP(PVT(E));
TMP ← SQRT(AA(E)↑2 + BB(E)↑2);
AA(E) ← AA(E)/TMP;
BB(E) ← BB(E)/TMP;
CC(E) ← CC(E)/TMP;{λ30;JUFA}
⊂4.2 Hide Marking a Coherent Object.⊃
OCCULT marks the faces, edges and vertices of a polyhedral
scene as being either visible or hidden with respect to a simulated
camera. Edges that were at first partially visible are split into
pieces so that each piece is either fully visible or fully hidden. In
a modeling environment that provides coherent polyhedra that can be
easily traveled and modified, the simple technique of hide marking
the neighbors of entities already hidden can be used to do almost all
of the actual hiding, once a starting place has been found.
In OCCULT, the two innermost routines, EHIDE and VHIDE,
perform this kind of marking. The routine VHIDE takes two arguments:
the vertex, V, which is to be marked as hidden and the face, F, that
is known to hide V; the routine then simply calls EHIDE for each
potentially visible edge of V's perimeter. EHIDE in turn takes three
arguments: an overface, F, an edge, E, and one vertex, V, of that
edge which is known to be hidden by F. EHIDE then checks to see
whether or not E leaves its overface, F, there are three basic cases:
(i) E does not leave F, so it is marked as hidden and VHIDE is
applied to the vertex OTHER(E,V); (ii) E does leave overface F by
crossing under a ¬FOLDED edge which provides a new overface for EHIDE
to check; or (iii) E leaves F by crossing under a <folded> edge, so
EHIDE splits the original edge, E, and the folded edge to form a
T-joint (defined in next paragraph) marking the hidden portion of E
as hidden and leaving the remaining portion of E potentially visible.
A T-joint occurs in the image, when a folded edge hides a
second edge that is further away from the camera. When OCCULT
discovers a T-joint, both edges are ESPLIT and two new vertices are
create the further one is called the JUT, Joint-Under-T vertex the
nearer one is called the JOT, Joint-Over-T vertex. Jut and Jots point
at each other using a TJOINT link field.
There are several techniques for finding starting places, the
major brute force technique involves doing an edge-edge or a
face-vertex compare using all the faces, edges and vertices that are
potentially visible. One minor technique, involves inspecting concave
corners for hidden edges which can be traced. Another minor technique
is applicible when hidden line elimination is being done on a
sequence of image which are not changing very drasticly from one to
the next; by saving a pointer to the overface that covered each
hidden vertex in the immediately preceding hidden line elimination,
the previous overface can be quickly checked to see if it still
covers the vertex. In one case, this form of exploiting
<frame-coherence> realized a twenty-five percent savings in
computation time.
⊂4.3 Edge-Edge and Face-Vertex Comparing.⊃
Although there are many interesting ways of comparing faces,
edges and vertices that are relevant to hidden line elimination; two
particular compares stand out as most basic, the edge-edge compare
and the face-vertex compare implemented in procedures named COMPEE
and COMPFE respectively.
The edge-edge compare routine, COMPEE, determines whether or
not two edges intersect in the 2-D image coordinates, XPP and YPP.
The basic edge-edge intersection test requires passing two opposition
conditions: the ends of one edge must be in opposite halfplane with
respect to the line containing the other edge and vice versa. The
halfplane opposition is determined by two evaluations of the normal
equation of the line using the edge coefficients AA, BB, CC and the
vertex coordinates XPP and YPP. Consquently, it can be assumed that the
two edges cross if the following expression both return negative values:
{λ7;JAF3
} FLAG1 ← (AA(E1)*XPP(PVT(E2)) + BB(E1)*YPP(PVT(E2)) + CC(E1))
XOR (AA(E1)*XPP(NVT(E2)) + BB(E1)*YPP(NVT(E2)) + CC(E1));
FLAG2 ← (AA(E2)*XPP(PVT(E1)) + BB(E2)*YPP(PVT(E1)) + CC(E2))
XOR (AA(E2)*XPP(NVT(E1)) + BB(E2)*YPP(NVT(E1)) + CC(E2));{λ30;JUFA}
\The infix operator XOR is for toggling the sign bits in the same
fashion as a multiplication would in more conventional ALGOL.
When the crossing condition is true, the locus of intersection can be
computed by solving two equations in two unknowns:
{λ7;JAF3
} TMP ← (AA(E1)*BB(E2) - AA(E2)*BB(E1));
XPP(V) ← (CC(E1)*BB(E2) - CC(E2)*BB(E1))/TMP;
YPP(V) ← (AA(E1)*CC(E2) - AA(E2)*CC(E1))/TMP;{λ30;JUFA}
An alternate edge-edge compare method would be to solve the
two equations in two unknowns first and then to see whether the
intersection locus is interior to the line segments of both edges.
Since, disjoint pairs of edges occur much more frequently than
intersecting edge, the alternate method requires more floating
arithmetic operations on the average than the first method which can
discover about half of the disjoint cases in computing, FLAG1.
Furthermore the alternate method does not lend itself to
distinguihing the almost touching cases.
{|;λ10;JAFA}
BOX 4.X {JC} Edge-Edge Compare Steps.
i. Test for Identity.
ii. Test for Topological connection.
(Edges already having a vertex of T-joint in common).
iii. Test for span Overlap in XPP and YPP.
To prevent nasty colinear cases.
iv. Compare for crossing ? Ends/Lines Opposition Tests.
v. Fudge (Move towards right and down).
{|;λ30;JUFA}
The face-vertex compare routine, COMPFE has two parts Z-depth
compare for vertex under the plane of the face and 2-D within compare
for vertex enclosure by the face perimeter. The first compare is done
by evaluating the Z-depth of the vertex with respect to the plane of
the face. Since faces are convex and since polyhedra are oriented the
properly directed edges coefficient can be used to test whether the
vertex falls outside of the face for any of the edges of the face's
perimeter. The Z-depth test is performed first because it is quicker.
Two very simple important kinds of hidden line eliminators
that almost work are based on combining edge-edge comparing or
face-vertex comparing with coherent object hidding.
⊂4.4 Recursive Windowing.⊃
Recursive Windowing is a two dimensional spatial sorting
technique for partitioning the faces, edges and vertices associated
with a rectangular region called a window into two subwindows.
recursively until a desired condition is achieved. The usual
termination condition is that the population of entites in the window
becomes sufficiently low or that the window becomes small. The idea
is implement in a routine called ESORT which resembles the hidden
line eliminators of [Warnock] and [Sutherland 68],
however ESORT is unique in that it maintains a data structure which
allows edges to be split during the sort. The potentially nasty
fixups are accomplished using a data structure that maintains a
coherent image of both windows and edges. Metaphorically, the data
structure is a cloth with a warp of windows and a woof of edges, each
thread bound to a fiber by a bead.
<Window Structure>. The sort window itself is a twelve word
node which contains data fields named XLO, XHI, YLO and YHI which
specify the boundary of the window and data fields named PENCNT,
SURCNT, EDGCNT and VCNT which specify the number of faces that
penetrate or surround the window, the number of edges that pass
through the window and the number of vertices that fall within the
window. The window contains sufficient link fields to hold pointers
to the head of the pen-face list, the sur-face list, the vertex
list, the head and tail of its edge list and a pointer to its
antecedent window.
<Bead Structure>. A bead is a two word node that contains
four pointers and which represents one instance of an edge passing
through a window. Each edge has a list of beads representing an
ordered list of the window through which it (the edge) passes; and
each window has a list of beads representing a list of the edges it
contains. The link fields named WND and EDG of a bead, point to the
particular window and the particular edge to which the bead belongs.
The link fields named WNBL and EDBL of a bead contain the necessary
links for the window's bead list and for the edge's bead list.
{|;λ10;JAFA}
BOX 4.X {JC} RECURSIVE WINDOWING ROUTINES.
1. MKSWN Make Sort Window.
2. PSHSWN Push Sort Window.
3. PENSUR Update penetrator and surrounder lists.
4. POPSWN Pop Sort Window.
5. BLED Bead List Edit.
{|;λ30;JUFA}
⊂4.5 Photometric Modeling and Video Generation.⊃
The light scattering properties of ordinary surfaces can be
modeled by thinking of the surface as composed of many little
mirrors. The orientation of each mirror is described by two angles,
its tilt from the normal vector of the surface and its pan about the
normal vector with respect to a specified reference vector in the
tangent plane of the surface. For a perfect reflecting surface all
the differential mirrors have a zero pan and tilt; for isotropic
conventional surfaces the statistical distribution of pan
orientations is flat and the distribution of tilt orientations is a
blip function; and for a perfect isotropic Lambert surfaces both the
pan and tilt distributions are flat.
(Propagating Underfaces and Shadows.)
⊂4.6 Performance of OCCULT and Related Work.⊃